package leetcode.editor.cn.q1_300.q100;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 没思路。。。查答案了
 *
 * @author qidi
 * @date 2022-01-12 10:53:22
 */
class Q0131_PalindromePartitioning {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<List<String>> ans;
        LinkedList<String> cur;
        int n;
        int[][] flags;

        public List<List<String>> partition(String s) {
            ans = new ArrayList<>();
            cur = new LinkedList<>();
            n = s.length();
            flags = new int[n][n];

            process(s, 0);

            return ans;
        }

        private void process(String s, int i) {
            if (i == n) {
                ans.add(new ArrayList<>(cur));
                return;
            }

            for (int j = i; j < n; j++) {
                if (isPalindrome(s, i, j) == 1) {
                    cur.add(s.substring(i, j + 1));
                    process(s, j + 1);
                    cur.removeLast();
                }
            }
        }

        // 记忆化搜索中，f[i][j] = 0 表示未搜索，1 表示是回文串，-1 表示不是回文串
        private int isPalindrome(String s, int i, int j) {
            if (flags[i][j] != 0) return flags[i][j];

            if (i >= j) {
                flags[i][j] = 1;
            } else if (s.charAt(i) == s.charAt(j)) {
                flags[i][j] = isPalindrome(s, i + 1, j - 1);
            } else {
                flags[i][j] = -1;
            }
            return flags[i][j];
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0131_PalindromePartitioning().new Solution();
        System.out.println(solution.partition("aab"));
    }
}